package com.yms.grap;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @version : 1.0
 * @author: yangmingsong
 * @date: 2022/9/9-09-09-15:53
 * @description: spring5-test 图的存储
 */
public class Test {
    public static void main(String[] args) {
//        邻接矩阵法
        int[] vex = {1,2,3,4,5};

        int[][] edge = {{Integer.MAX_VALUE,       10        ,Integer.MAX_VALUE,Integer.MAX_VALUE,      5          },
                        {Integer.MAX_VALUE,Integer.MAX_VALUE,        1,        Integer.MAX_VALUE,      2          },
                        {Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,     4           ,Integer.MAX_VALUE},
                        {7,Integer.MAX_VALUE,                     6           ,Integer.MAX_VALUE,Integer.MAX_VALUE},
                        {Integer.MAX_VALUE,       3        ,      9            ,     2           ,Integer.MAX_VALUE}};
        int vexnum = 5,arcnum=5;
        int[][] edg1 = {{0,1,0,1,0},{0,0,1,1,0},{0,0,0,0,1},{0,0,1,0,1},{0,0,0,0,0}};
        LjJz ljJzGrape = new LjJz(vex, edge, vexnum, arcnum);
        ljJzGrape.djstl(0);
        LjJz ljJzGrape1 = new LjJz(vex, edg1, vexnum, arcnum);
        ljJzGrape1.tpSorted();

//        邻接表法
        Integer[] vex1 = {1,2,3,4,5};
        int vexnum1 = 5,arcnum1=7;
        LjB.DdNode<Integer>[] vertices = new LjB.DdNode[5];
        LjB.BbNode bbNode01 = new LjB.BbNode(4, null);
        LjB.BbNode bbNode02 = new LjB.BbNode(1, bbNode01);
        vertices[0] = new LjB.DdNode<>(1, bbNode02);

        LjB.BbNode bbNode13 = new LjB.BbNode(3, null);
        LjB.BbNode bbNode12 = new LjB.BbNode(2, bbNode13);
        LjB.BbNode bbNode11 = new LjB.BbNode(4, bbNode12);
        LjB.BbNode bbNode10 = new LjB.BbNode(0, bbNode11);
        vertices[1] = new LjB.DdNode<>(2, bbNode10);

        LjB.BbNode bbNode21 = new LjB.BbNode(3, null);
        LjB.BbNode bbNode20 = new LjB.BbNode(1, bbNode21);
        vertices[2] = new LjB.DdNode<>(3, bbNode20);

        LjB.BbNode bbNode32 = new LjB.BbNode(2, null);
        LjB.BbNode bbNode31 = new LjB.BbNode(4, bbNode32);
        LjB.BbNode bbNode30 = new LjB.BbNode(1, bbNode31);
        vertices[3] = new LjB.DdNode<>(4, bbNode30);

        LjB.BbNode bbNode42 = new LjB.BbNode(1, null);
        LjB.BbNode bbNode41 = new LjB.BbNode(0, bbNode42);
        LjB.BbNode bbNode40 = new LjB.BbNode(3, bbNode41);
        vertices[4] = new LjB.DdNode<>(5, bbNode40);

        LjB<Integer> ljbGrape = new LjB<>(vertices, vexnum1, arcnum1,vex1);
        String s = ljbGrape.getBByNode(4);
        ljbGrape.BFSTraverse();
        System.out.println(s);
    }

}
//邻接矩阵法
class LjJz{
//    顶点表
    private int[] vex;
//    邻接矩阵表
    private int[][] edge;
//    图的当前顶点数和弧数
    private int vexnum,arcnum;
    private boolean[] flag ;

    public LjJz(int[] vex, int[][] edge, int vexnum, int arcnum) {
        this.vex = vex;
        this.edge = edge;
        this.vexnum = vexnum;
        this.arcnum = arcnum;
        flag = new boolean[vexnum];
        for(int i=0;i<vexnum;i++){
            flag[i] = false;
        }
    }
//    图的遍历，需借助一个辅助数组来标记这个节点是否遍历过
    public void BFSTraverse(){
        ArrayDeque<Integer> ts = new ArrayDeque<>();

        for (int i=0;i<vexnum;i++){
            if(!this.flag[i]){
                BFS(ts,i,this.vex[i]);
            }
        }
        ts.stream().forEach(e->{
            System.out.println(e);
        });
    }
    public void BFS(ArrayDeque<Integer> ts ,int index, int e){
        flag[index] = true;
        ts.add(e);
        for (int i=0;i<vexnum;i++){
            if((Integer) this.edge[index][i]==1){
                int vex = this.vex[i];
                if(!this.flag[i]){
                    flag[i] = true;
                    ts.add(vex);
                }
            }
        }

    }

    public int getIndex(int e){
        return Arrays.asList(this.vex).indexOf(e);
    }

//

    /** 对于带权图，且权值不存在负数 无限大的权值取值为Integer.MAX_VALUE
     * 迪杰斯特拉----寻求最短路径
     * @param index 开始顶点
     * @return
     */
    public void djstl(int index){
        int vi = this.vex[index];
        ArrayList<Integer> S = new ArrayList<>();
//        为了方便，这里存顶点的下标
        S.add(index);
        int[] dist =  new int[this.vexnum];
        for(int i=0;i<vexnum;i++){
            dist[i] = this.edge[0][i];
        }
        int i=1;
        while (i<=vexnum-1){
            int[] minDistAndIndex = getMinDistAndIndex(dist, S, vexnum);
            int j = minDistAndIndex[1];
            dist[j] = minDistAndIndex[0];
            S.add(j);
            System.out.println(JSONObject.toJSONString(S)+";dist:"+minDistAndIndex[0]);
            modifyMinDist(dist, S, vexnum,j);
            i++;
        }
    }

    private void modifyMinDist(int[] dist, ArrayList<Integer> s, int vexnum, int j) {
        for(int i=0;i<vexnum;i++){
            if(!s.contains(i) && this.edge[j][i]!=Integer.MAX_VALUE &&dist[j]+this.edge[j][i] < dist[i]){
                dist[i] = dist[j]+this.edge[j][i];
            }
        }
    }

    /**
     * 拓扑排序--有向无环图
     */
    public void tpSorted(){
        ArrayList<Integer> ints = new ArrayList<>();
        ArrayList<Integer> datas = new ArrayList<>();
        for(int j=0;j<vexnum;){
            if(!ints.contains(j)){
                int flag = 0;
                for(int i=0;i<vexnum;i++){
                    if(this.edge[i][j]==0){
                        flag++;
                    }
                }
                if(flag==vexnum){
                    for(int k=0;k<vexnum;k++){
                        this.edge[j][k] =0;
                    }
                    ints.add(j);
                    datas.add(this.vex[j]);
                    j = 0;
                }else {
                    j++;
                }
            }else {
                j++;
            }
        }
        if(ints.size()!=this.vexnum){
            System.out.println("有向图中存在回路");
        }else {
            System.out.println("拓扑排序为："+JSONObject.toJSONString(datas));
        }
    }


    public int[] getMinDistAndIndex(int[] dist, ArrayList<Integer> S, int vexnum){
        int[] data = new int[2];
        int min = (int) dist[0];
        int ix = 0;
        for(int i=1;i<vexnum;i++){
//            取最小值
            if(!S.contains(i)){
                if(min>dist[i]){
                    min = dist[i];
                    ix = i;
                }
            }
        }
        data[0] = min;
        data[1] = ix;
        return data;
    }
}

//邻接表法
class LjB<T>{

    private DdNode<T>[] vertices;

    //    顶点表
    private T[] vex;

    private int vexnum,arcnum;
    private boolean[] flag ;

    public LjB(DdNode<T>[] vertices, int vexnum, int arcnum,T[] vex) {
        this.vertices = vertices;
        this.vexnum = vexnum;
        this.arcnum = arcnum;
        this.vex = vex;
        flag = new boolean[vexnum];
        for(int i=0;i<vexnum;i++){
            flag[i] = false;
        }
    }

//    获取某个顶点的所有边
    public String getBByNode(T e){
        int index = Arrays.asList(this.vex).indexOf(e);
//        从顶点表中获取顶点
        DdNode<T> vertex = this.vertices[index];
//        首先获取边表节点
        BbNode bbNode = vertex.bbNode;
        StringBuilder stringBuilder = new StringBuilder();
        while (bbNode!=null){
//            如果不为空，获取边表节点的数据索引指向定点表数组中获取弧头元素
            T head = this.vertices[bbNode.adjvex].data;
            stringBuilder.append(vertex.data+"-->"+head+";");
            bbNode = bbNode.next;
        }
        return stringBuilder.toString();
    }

    //    图的遍历，需借助一个辅助数组来标记这个节点是否遍历过
    public void BFSTraverse(){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0;i<vexnum;i++){
            if(!flag[i]){
                DdNode<T> vertex = this.vertices[i];
                flag[i] = true;
                stringBuilder.append(vertex.data+"--");
                BbNode bbNode = vertex.bbNode;
                while (bbNode!=null){
                    if(!flag[bbNode.adjvex]){
                        T head = this.vertices[bbNode.adjvex].data;
                        flag[bbNode.adjvex] = true;
                        stringBuilder.append(head+"--");
                    }
                    bbNode = bbNode.next;
                }
            }
        }
        System.out.println(stringBuilder.toString());
    }

    //    边表节点
    static class BbNode{
//        该弧指向的顶点的位置
    private int adjvex;
//    指向下一条弧的指针
    private BbNode next;

    public BbNode(int adjvex, BbNode next) {
        this.adjvex = adjvex;
        this.next = next;
    }
}

//顶点表节点
    static class DdNode<T>{
//        顶点的数据
        private T data;
//        指向第一条依附该顶点的弧的指针
        private BbNode bbNode;

    public DdNode(T data, BbNode bbNode) {
        this.data = data;
        this.bbNode = bbNode;
    }
}
}
